package com.yequan.leetcode.linkedlist.reverselist_206;

import com.yequan.leetcode.linkedlist.ListNode;

/**
 * @author : Administrator
 * @date : 2020/3/16
 */
public class RecodeReverseList {

    /**
     * 遍历+逐个反转(迭代法)
     * 在遍历过程中,将当前节点的next指向其哪一个节点
     * 复杂度:
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public class Iteration {

        public ListNode reverseList1(ListNode head) {
            ListNode preNode = null;
            ListNode currentNode = head;
            while (currentNode != null) {
                ListNode tempNode = currentNode.next;
                currentNode.next = preNode;
                preNode = currentNode;
                currentNode = tempNode;
            }
            return preNode;
        }

        public ListNode reverseList2(ListNode head) {

            ListNode preNode = null;
            ListNode currentNode = head;
            while (currentNode != null) {
                ListNode tempNode = currentNode.next;
                currentNode.next = preNode;
                preNode = currentNode;
                currentNode = tempNode;
            }
            return preNode;
        }

        public ListNode reverseList3(ListNode head) {
            //用于记录前一个节点
            ListNode preNode = null;
            ListNode currentNode = head;
            while (currentNode != null) {
                ListNode tempNode = currentNode.next;
                //反转
                currentNode.next = preNode;
                preNode = currentNode;
                currentNode = tempNode;
            }
            return preNode;
        }

        public ListNode reverseList4(ListNode head) {
            ListNode preNode = null;
            ListNode currentNode = head;
            while (currentNode != null) {
                ListNode tempNode = currentNode.next;
                currentNode.next = preNode;
                preNode = currentNode;
                currentNode = tempNode;
            }
            return preNode;
        }

        public ListNode reverseList5(ListNode head) {

            ListNode preNode = null;
            ListNode currentNode = head;
            while (null != currentNode) {
                ListNode tempNode = currentNode.next;
                currentNode.next = preNode;
                preNode = currentNode;
                currentNode = tempNode;
            }
            return preNode;
        }

        public ListNode reverseList6(ListNode head) {
            ListNode preNode = null;
            ListNode currNode = head;
            while (currNode != null) {
                ListNode tempNode = currNode.next;
                currNode.next = preNode;
                preNode = currNode;
                currNode = tempNode;
            }
            return preNode;
        }

        public ListNode reverseList7(ListNode head) {
            ListNode preNode = null;
            ListNode currNode = head;
            while (currNode != null) {
                ListNode temp = currNode.next;
                currNode.next = preNode;
                preNode = currNode;
                currNode = temp;
            }
            return preNode;
        }

        public ListNode reverseList8(ListNode head) {
            ListNode preNode = null;
            ListNode currNode = head;
            while (currNode != null) {
                ListNode temp = currNode.next;
                currNode.next = preNode;
                preNode = currNode;
                currNode = temp;
            }
            return preNode;
        }

        public ListNode reverseList9(ListNode head) {
            ListNode preNode = null;
            ListNode currNode = head;
            while (currNode != null) {
                ListNode nextNode = currNode.next;
                currNode.next = preNode;
                preNode = currNode;
                currNode = nextNode;
            }
            return preNode;
        }

        public ListNode reverseList10(ListNode head) {
            ListNode preNode = null;
            ListNode currNode = head;
            while (currNode != null) {
                ListNode temp = currNode.next;
                currNode.next = preNode;
                preNode = currNode;
                currNode = temp;
            }
            return preNode;
        }

        public ListNode reverseList11(ListNode head) {
            if (head == null || head.next == null) {
                return null;
            }
            ListNode preNode = null;
            ListNode currentNode = head;
            while (currentNode != null) {
                ListNode nextNode = currentNode.next;
                currentNode.next = preNode;
                preNode = currentNode;
                currentNode = nextNode;
            }
            return preNode;
        }

        public ListNode reverseList12(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode preNode = null;
            ListNode currentNode = head;
            while (currentNode != null) {
                ListNode nextNode = currentNode.next;
                currentNode.next = preNode;
                preNode = currentNode;
                currentNode = nextNode;
            }
            return preNode;
        }

        public ListNode reverseList13(ListNode head) {
            if (null == head) {
                return null;
            }
            ListNode preNode = null;
            ListNode currentNode = head;
            while (currentNode != null) {
                ListNode nextNode = currentNode.next;
                head.next = preNode;
                preNode = currentNode;
                currentNode = nextNode;
            }
            return preNode;
        }

        public ListNode reverseList14(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode preNode = null;
            ListNode currentNode = head;
            while (currentNode != null) {
                ListNode nextNode = currentNode.next;
                currentNode.next = preNode;
                preNode = currentNode;
                currentNode = nextNode;
            }
            return preNode;
        }

        public ListNode reverseList15(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode preNode = null;
            ListNode currentNode = head;
            while (currentNode != null) {
                ListNode nextNode = currentNode.next;
                currentNode.next = preNode;
                preNode = currentNode;
                currentNode = nextNode;
            }
            return preNode;
        }

        public ListNode reverseList16(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode preNode = null;
            ListNode currentNode = head;
            while (currentNode != null){
                ListNode temp = currentNode.next;
                currentNode.next = preNode;
                preNode = currentNode;
                currentNode = temp;
            }
            return preNode;
        }
    }


}
